package com.fallsvc.dayproblem.demo202511;

import java.util.*;

/**
 * @auther falls_vc
 * description:
 * @date 2025/11/19  14:42
 */
public class Demo20251119 {
    public static void main(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();
        System.out.println(randomizedSet.remove(0));
        System.out.println(randomizedSet.remove(0));
        System.out.println(randomizedSet.insert(0));
        System.out.println(randomizedSet.getRandom());
        System.out.println(randomizedSet.remove(0));
        System.out.println(randomizedSet.insert(0));
    }

    static class RandomizedSet {
        private List<Integer> list;
        private Map<Integer,Integer> map;// <val,下标>
        private Random random;

        public RandomizedSet() {
            list = new ArrayList<>();
            map = new HashMap<>();
            random = new Random();
        }

        public boolean insert(int val) {
            if(map.containsKey(val)) return false;

            int index = list.size();
            list.add(val);
            map.put(val,index);
            return true;
        }

        public boolean remove(int val) {
            if(!map.containsKey(val)) return false;

            int index = map.get(val);
            int last = list.get(list.size() - 1);


            list.set(index,last);
            map.put(last,index);
            list.remove(list.size() - 1);
            map.remove(val);




            return true;
        }

        public int getRandom() {
            int size = list.size();
            // if(size == 0) return -1;
            return  list.get(random.nextInt(size));
        }
    }
    public static void main1(String[] args) {
        List<Integer> list = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        map.remove(1);
        Random random = new Random();
        random.nextInt(0,1);
    }

    //https://leetcode.cn/problems/o8SXZn/?envType=problem-list-v2&envId=greedy&difficulty=EASY
    // 蓄水

    public int storeWater(int[] bucket, int[] vat) {
        int n = bucket.length;
        // 最大蓄水次数
        int maxk = Arrays.stream(vat).max().getAsInt();
        if(maxk == 0) return 0;

        int res = Integer.MAX_VALUE;// 总操作次数

        for (int i = 1;i <= maxk && i < res; i++) {
            int t = 0;//扩水桶次数
            for(int j = 0; j < n;j++) {
                t += Math.max(0,(vat[j] - 1) / i + 1 - bucket[j]);// vat[j] - 1 合理化偶数不向上取整
            }
            res = Math.min(res,t + i);
        }
        return res;
    }

//    https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=problem-list
    // 中序和后序遍历创建二叉树


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public int prePostIndex;

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            prePostIndex = inorder.length - 1;

            return buildTreeChild(inorder, postorder, 0, inorder.length - 1);
        }

        public TreeNode buildTreeChild(int[] inorder, int[] postorder, int s, int e) {
            if (s > e || prePostIndex < 0) {
                return null;
            }
            int val = postorder[prePostIndex--];
            TreeNode root = new TreeNode(val);

            int index = findIndexValInInorder(inorder, val, s, e);
            if (index == -1) return null;

            root.right = buildTreeChild(inorder, postorder, index + 1, e);
            root.left = buildTreeChild(inorder, postorder, s, index - 1);

            return root;
        }

        public int findIndexValInInorder(int[] inorder, int val, int s, int e) {
            for (int i = s; i <= e; i++) {
                if (inorder[i] == val) {
                    return i;
                }
            }
            return -1;
        }
    }
}
